{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1331faa1",
   "metadata": {},
   "source": [
    "可以在[Bookshop.org](https://bookshop.org/a/98697/9781098155438) 和\n",
    "[Amazon](https://www.amazon.com/_/dp/1098155432?smid=ATVPDKIKX0DER&_encoding=UTF8&tag=oreilly20-20&_encoding=UTF8&tag=greenteapre01-20&linkCode=ur2&linkId=e2a529f94920295d27ec8a06e757dc7c&camp=1789&creative=9325)获取纸制版和电子版的*Think Python 3e*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56b1c184",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\n",
    "    filename = basename(url)\n",
    "    if not exists(filename):\n",
    "        from urllib.request import urlretrieve\n",
    "\n",
    "        local, _ = urlretrieve(url, filename)\n",
    "        print(\"Downloaded \" + str(local))\n",
    "    return filename\n",
    "\n",
    "download('https://gitee.com/regentsai/Think_Python_3e_CN/blob/master/thinkpython.py');\n",
    "download('https://gitee.com/regentsai/Think_Python_3e_CN/blob/master/b/master/diagram.py');\n",
    "\n",
    "import thinkpython"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88ecc443",
   "metadata": {},
   "source": [
    "# 第6章:返回值\n",
    "\n",
    "在之前的章节，我们使用过内建的函数（如`abs`和`round`），模块中的函数（如`sqrt`和`pow`）。当你调用这些函数时，它将返回值，你可以用返回的值赋值给变量，或者作为表达式的一部分。\n",
    "\n",
    "我们目前自己写的函数不同。有些使用`print`函数来打印值，有些使用海龟函数来绘图。但它们不返回值。\n",
    "\n",
    "本章我们将看到如何编写有返回值的函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cf2cf80",
   "metadata": {},
   "source": [
    "## 有些函数有返回值\n",
    "\n",
    "当你调用类似`math.sqrt`的函数，它们的结果称为**返回值return value**。如果函数调用在单元格的最后一行，Jupyter将立刻显示返回值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e0e1dd91",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.656366395715726"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "math.sqrt(42 / math.pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b4885c2",
   "metadata": {},
   "source": [
    "如果你将返回值赋值给变量，函数的返回值则不会被显示。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5aaf62d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "radius = math.sqrt(42 / math.pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "196c692b",
   "metadata": {},
   "source": [
    "但你可以稍后进行显示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "741f7386",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.656366395715726"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "radius"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "257b28d5",
   "metadata": {},
   "source": [
    "你也可以使用返回值作为表达式的一部分。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e56d39c4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.312732791431452"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "radius + math.sqrt(42 / math.pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23ed47ab",
   "metadata": {},
   "source": [
    "以下是有返回值的函数定义示例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "50a9a9be",
   "metadata": {},
   "outputs": [],
   "source": [
    "def circle_area(radius):\n",
    "    area = math.pi * radius**2\n",
    "    return area"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "273acabc",
   "metadata": {},
   "source": [
    "`circle_area`接受`radius`作为半径，计算给定半径圆的面积。\n",
    "\n",
    "最后一行是`return`语句，返回`area`的值。\n",
    "\n",
    "如果我们像下面一样调用函数，Jupyter将显示返回值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d70fd9b5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42.00000000000001"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circle_area(radius)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f28bfd6",
   "metadata": {},
   "source": [
    "我们可以将返回值赋值给变量："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ef20ba8c",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = circle_area(radius)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f82fe70",
   "metadata": {},
   "source": [
    "或者将返回值作为表达式的一部分："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0a4670f4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "63.000000000000014"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "circle_area(radius) + 2 * circle_area(radius / 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15122fd2",
   "metadata": {},
   "source": [
    "同样，我们也可以查看被返回值赋值变量的值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "6e6460b9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42.00000000000001"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3f6dcae",
   "metadata": {},
   "source": [
    "但我们不能访问`area`变量。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "77613df9",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'area' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31mNameError\u001b[0m\u001b[0;31m:\u001b[0m name 'area' is not defined\n"
     ]
    }
   ],
   "source": [
    "%%expect NameError\n",
    "\n",
    "area"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8ace9ce",
   "metadata": {},
   "source": [
    "`area`是函数中的局部变量，我们无法在函数外部访问。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41a4f03f",
   "metadata": {},
   "source": [
    "## 有些函数返回None\n",
    "\n",
    "如果函数没有`return`语句，它将返回`None`。`None`和`True`与`False`类似，也是一个特殊的值。例如，以下是第3章的`repeat`函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "89c083f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def repeat(word, n):\n",
    "    print(word * n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ada19cf",
   "metadata": {},
   "source": [
    "如果我们像下面一样调用它，将展示“Finland”歌词的第1行："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "737b67ca",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finland, Finland, Finland, \n"
     ]
    }
   ],
   "source": [
    "repeat('Finland, ', 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe49f5e5",
   "metadata": {},
   "source": [
    "该函数使用`print`显示字符串的值，但它本身不使用`return`语句返回值。如果我们将结果赋值给变量，它也会显示字符串的值。\n",
    "\n",
    "译注：与之前章节的描述不同，赋值语句实际上可能会有可见的影响。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "9b4fa14f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finland, Finland, Finland, \n"
     ]
    }
   ],
   "source": [
    "result = repeat('Finland, ', 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ecabbdb",
   "metadata": {},
   "source": [
    "如果我们打印变量的值，不会显示任何信息："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "50f96bcb",
   "metadata": {},
   "outputs": [],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07033959",
   "metadata": {},
   "source": [
    "`result`实际上有值，但Jupyter不会显示它。我们可以像这样显示它的值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "6712f2df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "379b98c5",
   "metadata": {},
   "source": [
    "`repeat`函数的返回值为`None`。\n",
    "\n",
    "下面是与`repeat`类似的函数，不同的是它有返回值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "0ec1afd3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def repeat_string(word, n):\n",
    "    return word * n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db6ad3d4",
   "metadata": {},
   "source": [
    "注意我们可以在`return`语句中使用表达式，而不只是变量。\n",
    "\n",
    "我们可以用这个版本的函数返回值赋值给变量。当函数运行时，它不会显示任何东西。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "c82334b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "line = repeat_string('Spam, ', 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1232cd8a",
   "metadata": {},
   "source": [
    "但我们可以显示赋值给`line`变量的值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "595ec598",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Spam, Spam, Spam, Spam, '"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "line"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae02c7d2",
   "metadata": {},
   "source": [
    "只返回值，不显示任何东西或者有其他影响的函数称为**纯函数pure function**。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "567ae734",
   "metadata": {},
   "source": [
    "## 返回值和条件\n",
    "\n",
    "如果Python不提供`abs`函数，我们可以像这样编写它："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "236c59e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    else:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffd559b8",
   "metadata": {},
   "source": [
    "若`x`为负数，执行第一个分支，第一个`return`语句返回`-x`的值，函数立刻结束；否则，执行第二个分支，第二个`return`语句返回`x`的值，函数结束。这个函数是正确的。\n",
    "\n",
    "然而，如果你在条件语句中使用了`return`语句，你需要确保每个可能的分支都可以通往`return`语句。例如以下是`absolute_value`的错误版本。\n",
    "\n",
    "译注：这个要求是对纯函数的要求。纯函数从设计目的上必须返回值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "2f60639c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value_wrong(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    if x > 0:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da3280ae",
   "metadata": {},
   "source": [
    "把`0`作为参数调用函数时，将发生："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "c9dae6c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "absolute_value_wrong(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5733f239",
   "metadata": {},
   "source": [
    "我们没有得到任何东西！问题在于：当`x`为0时，没有一个条件正确，函数没有遇到任何`return`语句，因此返回值为`None`，所以Jupyter不会显示任何东西。\n",
    "\n",
    "另外一个错误版本的`absolute_value`在函数定义结尾有额外的`return`语句："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "c8c4edee",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value_extra_return(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    else:\n",
    "        return x\n",
    "    \n",
    "    return '这是死代码(dead code)。'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf5486fd",
   "metadata": {},
   "source": [
    "如果`x`为负数，执行第一个`return`语句，函数结束；否则执行第二个`return`语句，函数结束。无论如何，都无法到达第三个`return`语句，这个语句永远不会执行。\n",
    "\n",
    "永远不会执行的代码称为**死代码dead code**。总体而言，死代码没有害处，但通常表明你对程序存在误解，也可能会让其他尝试理解程序的人感到困惑。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68a6ae39",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 增量开发\n",
    "\n",
    "当你编写更大的函数时，你可能发现你花了更多时间调试。要处理日益增长的复杂程序，你可能需要尝试**增量开发incremental development**，一次增加一小部分代码并进行测试。\n",
    "\n",
    "比如，假设你想要算出坐标为$(x_1, y_1)$和$(x_2, y_2)$的两点之间的距离。距离公式为：\n",
    "\n",
    "$$\\mathrm{distance} = \\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$\n",
    "\n",
    "第一步需要考虑，在Python中`distance`函数应该是怎样的，即输入（形参）和输出（返回值）是什么？\n",
    "\n",
    "对于这个函数，输入是点的坐标，输出值是距离。你可以立刻编写函数的框架："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "bbcab1ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b384fcf",
   "metadata": {},
   "source": [
    "这个版本还没有计算距离，它总是返回0。但它是一个有返回值的完整函数，你可以在它变得更复杂之前进行测试。\n",
    "\n",
    "要测试新函数，我们用以下样本参数进行调用："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "923d96db",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13a98096",
   "metadata": {},
   "source": [
    "我选择这些值，让水平距离为`3`，垂直距离为`4`。结果应该为`5`，对应`3-4-5`直角三角形的斜边。当测试函数时，知道正确答案会很有用。\n",
    "\n",
    "在这时我们确认了函数可以运行，并返回了值。我们可以开始在函数体中添加代码。\n",
    "\n",
    "下一步，计算`x2 - x1`和`y2 - y1`的值是合理的。以下是使用临时变量存储这些值并显示它们的一版函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "9374cfe3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    print('x的差值dx是', dx)\n",
    "    print('y的差值dy是', dy)\n",
    "    return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c342a3bd",
   "metadata": {},
   "source": [
    "如果函数正常生效，应该显示`x的差值dx是3`和`y的差值dy是4`。如果确实如此，那么函数获得了正确的参数，并正确执行了第一步计算。否则，也只需要检查很少的几行代码。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "405af839",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x的差值dx是 3\n",
      "y的差值dy是 4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9424eca9",
   "metadata": {},
   "source": [
    "目前为止进展不错。下一步我们计算`dx`和`dy`的平方和："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "e52b3b04",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    dsquared = dx**2 + dy**2\n",
    "    print('距离的平方和dsquared为: ', dsquared)\n",
    "    return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e28262f9",
   "metadata": {},
   "source": [
    "再次，我们可以调用函数并检查输出，结果应该为25。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "38eebbf3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "距离的平方和dsquared为:  25\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c09f0ddc",
   "metadata": {},
   "source": [
    "最后，我们可以使用`math.sqrt`计算距离："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "b4536ea0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    dsquared = dx**2 + dy**2\n",
    "    result = math.sqrt(dsquared)\n",
    "    print(\"结果为\", result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f27902ac",
   "metadata": {},
   "source": [
    "并进行测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "325efb93",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "结果为 5.0\n"
     ]
    }
   ],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ad2e626",
   "metadata": {},
   "source": [
    "结果正确，但这个版本打印结果而不是返回结果，所以返回值是`None`。\n",
    "\n",
    "通过将`print`函数替换为`return`语句可以修复这个问题。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "3cd982ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    dsquared = dx**2 + dy**2\n",
    "    result = math.sqrt(dsquared)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3a13a14",
   "metadata": {},
   "source": [
    "这个版本的`distance`是纯函数。如果我们像下面一样调用函数，只会显示结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "c734f5b2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7db8cf86",
   "metadata": {},
   "source": [
    "如果我们将结果赋值给变量，不会显示任何信息。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "094a242f",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = distance(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c3b8829",
   "metadata": {},
   "source": [
    "我们编写的`print`语句对于调试很有用，但一旦函数正常工作，我们就可以移除它。这种代码称为**脚手架scaffolding**，它对构建代码很有用，但不是最终成品的一部分。\n",
    "\n",
    "这个例子展示了增量开发过程。该过程的核心步骤为：\n",
    "\n",
    "1. 从可以运行的程序开始，做出小的改变，然后在每次改变后进行测试；\n",
    "2. 使用变量维护临时的值，以便展示和检查；\n",
    "3. 当程序编写完成，移除脚手架。\n",
    "\n",
    "在任何时候，如果出现了错误，它出现的位置通常是你刚做出改变的位置。增量更新可以节省很多调试时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dd7514f",
   "metadata": {},
   "source": [
    "## 布尔函数\n",
    "\n",
    "函数可以返回布尔值`True`与`False`，便于将复杂测试封装进函数中。例如`is_divisible`检查`x`能否被`y`整除。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "64207948",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_divisible(x, y):\n",
    "    if x % y == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c73d69d8",
   "metadata": {},
   "source": [
    "译注：返回布尔值的函数名习惯上为“is_实词”。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3a58afb",
   "metadata": {},
   "source": [
    "以下是调用该函数的示例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "c367cdae",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_divisible(6, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "837f4f95",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_divisible(6, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9103ece",
   "metadata": {},
   "source": [
    "在函数内，`==`运算符的结果是布尔值，所以我们可以更简洁地编写函数，直接返回这个表达式。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "e411354f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_divisible(x, y):\n",
    "    return x % y == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d82dae5",
   "metadata": {},
   "source": [
    "布尔函数通常用在条件语句中："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "925e7d4f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "可以被整除\n"
     ]
    }
   ],
   "source": [
    "if is_divisible(6, 2):\n",
    "    print('可以被整除')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e232afc",
   "metadata": {},
   "source": [
    "你可能会写这样的语句："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "62178e75",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "可以被整除\n"
     ]
    }
   ],
   "source": [
    "if is_divisible(6, 2) == True:\n",
    "    print('可以被整除')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff9e5160",
   "metadata": {},
   "source": [
    "但是这个比较是没有必要的。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a932a966",
   "metadata": {},
   "source": [
    "## 用返回值进行递归\n",
    "\n",
    "既然我们可以编写有返回值的函数，就可以编写有返回值的递归函数。有了这种能力，我们就通过了一个重要的门槛，我们目前介绍的Python的子集是**图灵完备Turing complete**的，即我们可以执行任何算法描述的计算。\n",
    "\n",
    "要展示带有返回值的递归函数，我们将计算几个递归定义的数学问题。递归的定义类似于循环定义，因为定义指向被定义的事物。真正的循环定义并不有用：\n",
    "\n",
    "> vorpal:形容词，描述某个东西很vorpal。\n",
    "\n",
    "如果你看到词典中这样定义，你可能会生气。另一方面，如果你查看阶乘函数(用$!$符号表示)的定义，你可能会得到以下描述：\n",
    "\n",
    "$$\\begin{aligned}\n",
    "0! &= 1 \\\\\n",
    "n! &= n~(n-1)!\n",
    "\\end{aligned}$$ \n",
    "\n",
    "这个定义说$0$的阶乘是$1$，其他$n$的阶乘是用$n$乘以$n-1$的阶乘。\n",
    "\n",
    "如果你能够写出某个事物的递归定义，你就可以编写Python程序来计算它。按照增量开发过程，我们将定义一个函数，接受`n`为参数，总是返回`0`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "23e37c79",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee1f63b8",
   "metadata": {},
   "source": [
    "现在让我们开始第一部分的定义，如果参数恰好为`0`，我们只需要返回`1`："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "5ea57d9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f2fd7c7",
   "metadata": {},
   "source": [
    "现在让我们填充第二部分，如果`n`不为`0`，我们需要进行递归调用，计算`n-1`的阶乘，并乘以`n`："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "b66e670b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        recurse = factorial(n-1)\n",
    "        return n * recurse"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da3d1595",
   "metadata": {},
   "source": [
    "这个程序的执行流程与第5章的`countdown`类似。如果我们用参数`3`调用`factorial`：\n",
    "\n",
    "由于`3`不为`0`，我们接受第2个分支，计算`n-1`的阶乘\\...\n",
    "\n",
    "> 由于`2`不为`0`，我们接受第2个分支，计算`n-1`的阶乘\\...\n",
    ">\n",
    "> > 由于`1`不为`0`，我们接受第2个分支，计算`n-1`的阶乘\\...\n",
    "> >\n",
    "> > > 由于`0`等于`0`，我们接受第1个分支，返回`1`，不再递归调用\n",
    "> >\n",
    "> > 返回值`1`乘以`n`(`n`为`1`),返回结果`1`\n",
    ">\n",
    "> 返回值`1`乘以`n`(`n`为`2`),返回结果`2`\n",
    "\n",
    "返回值`2`乘以`n`(`n`为`3`),返回结果`6`。结果`6`是整个函数调用过程的返回值。\n",
    "\n",
    "下面的栈图显示了这个函数调用的序列。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "455f0457",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import Frame, Stack, make_binding\n",
    "\n",
    "main = Frame([], name='__main__', loc='left')\n",
    "frames = [main]\n",
    "\n",
    "ns = 3, 2, 1\n",
    "recurses = 2, 1, 1\n",
    "results = 6, 2, 1\n",
    "\n",
    "for n, recurse, result in zip(ns, recurses, results):\n",
    "    binding1 = make_binding('n', n)\n",
    "    binding2 = make_binding('recurse', recurse)\n",
    "    frame = Frame([binding1, binding2], \n",
    "                  name='factorial', value=result,\n",
    "                  loc='left', dx=1.2)\n",
    "    frames.append(frame)\n",
    "    \n",
    "binding1 = make_binding('n', 0)\n",
    "frame = Frame([binding1], name='factorial', value=1, \n",
    "              shim=1.2, loc='left', dx=1.4)\n",
    "frames.append(frame)\n",
    "\n",
    "stack = Stack(frames, dy=-0.45)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "a75ccd9b",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAASYAAAD2CAYAAAB7jSpBAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjkuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8hTgPZAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAp00lEQVR4nO3df1RU9Z/H8ScDgyTu+CuOKJSaueIPcBAUBpSAiMBQ8xw56qJs6pE8peSaHtf0dNRWl8rUVSw0PUqoe3b9kUiZJqbG0Dkoa/jjS8vqEBaQ+CPs6w9Axrn7B8tdUEFmHIax7/vx13WY+/nc6caLz73zue+Pi6IoCkII4UQ0HX0AQgjxIAkmIYTTkWASQjgdCSYhhNORYBJCOB0JJiGE05FgEkI4HQkmIYTTkWASQjgdCSYhhNORYBJCOB0JJiGE05FgEkI4HQkmIYTTkWASQjgdCSYhhNORYBJCOB0JJiGE05FgEkI4HQkmIYTTcevoA3ga3Lp1y67t/d3f/Z1d2xPiz0ZGTEIIpyPBJIRwOhJMQginI8EkhHA6T00wZWRksG7duo4+DCGEA7jIEuGPJ9/KCeFYDhkxubi48K//+q+MGjWKF154gdzcXJYsWUJgYCBDhw7lL3/5CwBXrlwhKiqKoKAghg4dSmpqKo25uXz5chYuXAjAjh07ePXVV5k6dSr+/v4EBwdTWlrqiI8ihHAAh13K6XQ6Tp06xYcffsiECRMYPXo0P/74I//4j//IqlWrAOjWrRs5OTn813/9F+fOnaO0tJR9+/Y9sr2CggLS0tI4f/48MTExfPjhh476KEKIduawYJo8eTIAI0aMQKPR8NprrwEQFBSkjnYsFguLFy9m+PDhBAYGUlhYSFFR0SPbGz16NH379gXAYDBgMpna/0MIIRzCYTO/PTw8AHB1daVTp07q666urpjNZgDWrl3LjRs3KCgowMPDgwULFlBbW9tqew+2IYR4+jnVt3LV1dV4e3vj4eFBVVUVe/bs6ehDEkJ0AKd6Vi41NZXExET0ej0+Pj7ExMR09CEJITqATBdoA5kuIIRjOdWlnBBCgI2XclevXiU2NrbZa+fOnWPAgAF4eno2e33fvn0MGDDA9iO0wqFDh3jvvfceer2kpIRBgwY1e6179+4cP37cIcclhLCOXMq1gVzKib9FpaWlGI1GoqOj8fX1dWjfciknhHgkT09PysrK2LZtGzk5OdTU1DisbwkmIcQj9erVC4PBAMCZM2f49NNP+fXXXx3StwSTEKJFkZGRdO3aFYA7d+6wfft28vPzae87QHKPSQjRqrNnz3LgwIFmr7344otMnDiRzp07t0ufMmISQrRq2LBhD31hYzKZ+Oyzz/jtt9/apU8JJiFEq1xdXRk9enSz1xRFUS/tLl++bPc+JZiEEI8VGBjIM8880+w1RVGor68nKyvL7iMnCSYhxGNptVoMBgMuLi4P/axz5864udn3sVsJJiFEmwwePFj9Nq4xoPr06cO8efPw8vKya18STEKINunZsyc6nQ6A/v37A1BZWcnt27ft3pdMFxBCtFllZSUWiwVfX1+2bt1KRUUFY8aMITo62q79yIhJCNFmffr0UZ+bCw0NBSAvL8/uEy4lmIQQNmlasaOsrMyubUswCSFsotVqCQwMBOCnn3566Od1dXXMnTuXgQMHMnToUKZNm9bmtp2qtK4Q4uny/PPP8+OPP1JeXv7Qz/75n/8ZjUbD//zP/+Di4mLVXCcJJiGEzZ599lmAh0KncVZ4eXm5OrWgd+/ebW5XLuWEEDZrDCagWb0mk8lEz549+Zd/+ReCg4MZM2YMx44da3O7EkxCCJs1Xd+xrq5O3a6vr6e0tJQhQ4ZQWFhIeno6U6ZM4dq1a21qV4JJCGGz+/fvq9vu7u7qdt++fdFoNCQlJQEwfPhw+vfvz1/+8pc2tSvBJISwWdNRUtNgevbZZ3n55Zc5cuQIAJcvX+bnn39+aFGQlsjNbyGEze7cuaNuu7q6NvtZRkYGM2fOZPHixbi6urJly5Y23wCXYBJC2OyXX34BwMvL66HKAy+88AInTpywqV25lBNC2MxkMgHg5+dn13ZlxPR/7L12nBBPI2vWPLRYLOqM78ZqA/YiIyYhhE2Ki4vV7eeee86ubUswCSGspigK3377LQARERFSwVII0fFMJpN6+yMkJMTu7UswCSGsYjab+fLLLwEYOXJku6wtJ8EkhLDKyZMnuXv3LgAvvfRSu/QhwSSEaLOKigqMRiMAiYmJeHp6tks/EkxCiDapqakhMzMTaFgxZciQIe3WlwSTEOKxzGYzmZmZ1NfXA5CQkNCu/UkwCSFapSgKe/fupaqqCoA5c+a0yw3vpqwOpuzsbAYPHoxer+f8+fNW7Xvz5k0++ugja7tUHTx4kEWLFj32fcuXL2fhwoU29/NnN2HCBAwGA+Hh4bz66qucO3euow9J2EltbS1Tp04lMDCQ8PBwJk6cyOXLl21uT1EUjhw5QklJCQDJycn06tXLXofbIqvXlYuPj2fmzJkkJiZa3VlZWRnBwcFcv37d6n3NZnObJ3EtX76c27dvs2bNmja3/7f0SMrNmzfp1q0bAF999RUffvgheXl5HXtQTVhzrm1hsVgA0Gj+fBcMtbW1nDx5ktjYWFxcXNi8eTOHDh0iOzu7Tfs3fSSlMZQKCgoAmDhxIgEBAe1y3A+y6sykpqaSl5fH4sWLCQsLY9q0aQQHBxMQEEBCQgJXr15V37t9+3b0ej3Dhw8nODiYsrIy5syZw82bN9Hr9QQHBwNw6dIlYmJiCAgIQK/Xc+DAAbUNFxcXPvnkEyIjI1myZAk7duxg0qRJAFy5coWoqCiCgoIYOnQoqampdl/bqiU6nY5169YRFRWFv78/O3fudEi/LSkrK2P37t0UFxerv3StaQwlgD/++MMpfkF1Oh0bN25k7NixLF++nFu3bjFv3jwiIyMxGAzMnz9fvb9RWVnJ9OnTMRgMGAwGPvjgA6DhEmPz5s1qm0uXLmX16tUArF69mtmzZ5OUlER4eDhXrlzh3XffJSgoiLCwMCIiIqitrQUgNzeX2NhYIiIiiIqKIj8/38H/NZqz5vx6eHjw6quvqk/6jxw50uallb7//ns1lOLj4x0WSmDlQ7wbNmzg3LlzLFy4kISEBK5fv67W/E1LS2PlypWkp6dz4sQJVq1aRV5eHr1791bnPGRkZBAcHExRUZHaZlJSErNmzSIlJYWLFy8SGhpKUFCQ+uxNXV2dWjphx44d6n7dunUjJyeHLl26cP/+fSZMmMC+ffvU4GpvnTp14vjx45SUlBAVFcWUKVPa9a98a7y8vPD09OTw4cMUFBQQEhKCn59fq4GTkpKijpL279/vqENtVV1dHYcOHQIa/giGhYWxceNGFEVh3rx5bN68mblz5zJ79mxiY2PJysoCaPMIPC8vj7y8PLy8vDh79iwnT57k9OnTaDQa/vjjD9zd3fn5559JS0tj//796HQ6TCYTY8eO5cKFC2i12nb77K2x5fw2ysjIID4+3qZ+G5cDHzduHCNGjLCpDVs90W/Srl27yMrKoq6ujpqaGry9vQH4+uuvSU5OVotCtXSj7NatWxQVFTFr1iwABg4cyOjRozEajUydOhWAmTNnPnJfi8XC4sWLMRqNKIrC1atX0ev1DgumyZMnAw2L/rm5uVFVVYWPj0+z95w6dYrKykqHHA+Aj48P1dXVHD58mGPHjpGYmKiekwdt2bIFaDiHy5YtY9++fQ47zpZMnz5d3f7qq684ffo06enpQMNX1Vqtltu3b1NQUNDs0qRpQfzWxMXF4eXlBUC/fv2or6/nrbfeYsyYMcTFxaHRaMjNzaW0tPShX+by8vKHnqB35vMLsGbNGkwmE+vXr7epv8DAQIYNG9YhgWxzMBmNRtLT0/nhhx/w8vLi4MGDrFy50qo2Gi+9Hiww1fTfXbp0eeS+a9eu5caNGxQUFODh4cGCBQvUobgjdOrUSd3WaDSYzWaH9W1PSUlJ/NM//RM3btygZ8+eHXosTSfrKYrC7t27HwqD27dvt7i/m5tbsxrUtbW1zdpsut21a1dOnTqF0WgkLy+PFStW8M0336AoCjExMWpwP602bNhATk4O2dnZT/QNWkeNEm0OpurqanQ6HT169ODevXvNru3HjRvHzJkzSUlJwdvbW72U0+l03L17V725qdPp0Ov1ZGZmMmPGDEwmE/n5+epfycf17+3tjYeHB1VVVezZs0cdxTiLUaNGOaSfO3fucPToUSoqKujevTsREREtDvX/+te/cufOHXU0m5OTQ48ePejRo4dDjrWtxo4dy7p161i7di1ubm5UV1fz+++/M2DAAAwGA5s2beKdd94BUG8p9O/fn8LCQgBu3LjB0aNHmTJlyiPbv379OhqNhpdffpno6GiMRiMlJSVER0eTlpZGcXGxOoGwsLBQvSfalDOeX4D09HT27t1LdnZ2s/uJTxObgyk+Pp6dO3fi5+eHr68vYWFhauHxiIgIli1bpn4z4O7uzt69e+nbty9JSUn4+/vj6elJYWEhu3bt4s0332T9+vW4uLiwdevWNtV2SU1NJTExEb1ej4+PDzExMbZ+lKfetWvXuHv3LnFxcY+99/DXv/6VadOmUVtbi0aj4dlnn+U///M/Hxq1drS0tDTef/99wsPD0Wg0aLVaVqxYwYABA9iyZQuLFi1i1KhRuLm58dprr7F06VJmzJhBcnIyoaGh9O/fn6CgoBbbLy8vJzU1lfr6eiwWCyEhIbzyyitotVo+//xz5s6dS21tLffu3WP48OFs27bNgZ++OWvOb0VFBe+99x79+vVTJ0G6u7tz/PhxRx2uXVg9XeDP6m9puoAQLbGmgmV76vjviYUQ4gESTEIIpyPBJIR4pNLSUr744gvKy8sd3rcEkxDikTw9PSkrK2Pbtm3k5ORQU1PjsL4lmIQQj9SrVy8MBgMAZ86c4dNPP+XXX391SN8STEKIFkVGRtK1a1egYT7V9u3byc/Pb/fnUiWYhBAt0mq1REVFAQ2z8RVFITc3l927d6sTp9uDBJMQolXDhg17aH6TyWTis88+47fffmuXPiWYhBCtcnV1ZfTo0c1eUxRFvbR7kkJ0LZFgEkI8VmBgIM8880yz1xRFob6+nqysLLuPnCSYhBCPpdVqMRgMj3ymsnPnznavRdYxlc2ckLM8IySEsxo8eDDfffcd0FCaSFEU+vTpwxtvvGH38igyYhJCtEnPnj3VqpaNdbIqKytbrZFlK6kuIIRos8rKSiwWC76+vmzdupWKigrGjBlDdHS0XfuREZMQos369OmDr68vAKGhoUBDLXV7j28kmIQQNhk0aJC6betKLC2RYBJC2ESr1RIYGAjATz/91OxntbW1vP766/z93/89er2euLg4q8JLgkkIYbPnn38e4JGlUVJSUigpKaGoqIiEhARSUlLa3K4EkxDCZo1LZz04wdLDw4OxY8eq855CQ0MpLS1tc7sSTEIImzVd06+1ek0bNmxg3LhxbW5XJlgKIWzm4eGhbtfV1T302Ao0LM9+8eJFMjIy2tyuBJMQwmZNFxh1d3d/6Odr1qxh//795ObmWrXwpgSTEMJmdXV16vaDwbR27Vr+/d//ndzcXKsX3pRgEkLY7M6dO+q2q6urul1eXs67777LCy+8oBaa69SpEwUFBW1qV4JJCGGzX375BQAvL69mlQd8fX2faDa4fCsnhLCZyWQCwM/Pz67tyojp/8gS4UJYV/7HYrGoM74bqw3Yi4yYhBA2KS4uVrefe+45u7YtwSSEsJqiKHz77bcARERE2L2CpQSTEMJqJpNJvf0REhJi9/YlmIQQVjGbzXz55ZcAjBw50qqJk20lwSSEsMrJkyfVxS5feumldulDgkkI0WYVFRUYjUYAEhMT8fT0bJd+JJiEEG1SU1NDZmYm0LBiypAhQ9qtLwkmIcRjmc1mMjMzqa+vByAhIaFd+5NgEkK0SlEU9u7dS1VVFQBz5sxplxveTVkdTNnZ2QwePBi9Xs/58+et2vfmzZt89NFH1napOnjwIIsWLXrs+5YvX87ChQtt7ufPrLa2lqlTpxIYGEh4eDgTJ05sl7XnRcdYtGgRw4YNQ6fTNZsAaStFUThy5AglJSUAJCcn06tXrydu93GsDqaMjAxWrlxJUVER/v7+Vu37JMFkNpsZP348H3/8sU37i//3xhtvcObMGfLz84mLiyM1NbWjD6kZs9ncru1bLBYsFku79tFRXn/9dY4cOaLW4n4SjaHUWBFg4sSJdn/0pCVWBVNqaip5eXksXryYsLAwpk2bRnBwMAEBASQkJHD16lX1vdu3b0ev1zN8+HCCg4MpKytjzpw53Lx5E71eT3BwMACXLl0iJiaGgIAA9Ho9Bw4cUNtwcXHhk08+ITIykiVLlrBjxw4mTZoEwJUrV4iKiiIoKIihQ4eSmppq97WtWqLT6Vi3bh1RUVH4+/uzc+dOh/TbkrKyMnbv3k1xcfFjf+E8PDx49dVX1SfBR44cafeld2yh0+nYuHEjY8eOZfny5dy6dYt58+YRGRmJwWBg/vz56v2NyspKpk+fjsFgwGAw8MEHHwANlxibN29W21y6dCmrV68GGqoozp49m6SkJMLDw7ly5QrvvvsuQUFBhIWFERERQW1tLQC5ubnExsYSERFBVFQU+fn5Dv6v0Zw15zc8PBwfHx+79Pv999+roRQfH09AQIBd2m0Lq+aRb9iwgXPnzrFw4UISEhK4fv26WvM3LS2NlStXkp6ezokTJ1i1ahV5eXn07t1bnfOQkZFBcHAwRUVFaptJSUnMmjWLlJQULl68SGhoKEFBQeqzN3V1dZw4cQKAHTt2qPt169aNnJwcunTpwv3795kwYQL79u1Tg6u9derUiePHj1NSUkJUVBRTpkyx+7T8tvLy8sLT05PDhw9TUFBASEgIfn5+aDSP/7uTkZFBfHy8A47y8erq6jh06BDQ8EcwLCyMjRs3oigK8+bNY/PmzcydO5fZs2cTGxtLVlYWANevX29T+3l5eeTl5eHl5cXZs2c5efIkp0+fRqPR8Mcff+Du7s7PP/9MWloa+/fvR6fTYTKZGDt2LBcuXECr1bbbZ2/Nk5zfJ9G4HPi4ceMYMWJEu/b1oCf6Tdq1axdZWVnU1dVRU1ODt7c3AF9//TXJycn07t0boMUbZbdu3aKoqIhZs2YBMHDgQEaPHo3RaGTq1KkAzJw585H7WiwWFi9ejNFoRFEUrl69il6vd1gwTZ48GWhY9M/NzY2qqqqH/lKdOnWKyspKhxwPgI+PD9XV1Rw+fJhjx46RmJionpNHWbNmDSaTifXr1zvsGFszffp0dfurr77i9OnTpKenAw1fVWu1Wm7fvk1BQQHZ2dnqe5sWxG9NXFwcXl5eAPTr14/6+nreeustxowZQ1xcHBqNhtzcXEpLSx8K6/Ly8ocuY5z9/D6pwMBAhg0b1iGBbHMwGY1G0tPT+eGHH/Dy8uLgwYOsXLnSqjYaL72aFph68N9dunR55L5r167lxo0bFBQU4OHhwYIFC9ShuCN06tRJ3dZoNO1+X8TeNmzYQE5ODtnZ2e3+DUtbNZ2spygKu3fvfigMbt++3eL+bm5uzWpQ19bWNmuz6XbXrl05deoURqORvLw8VqxYwTfffIOiKMTExLBlyxZ7fKSnXkeNEm0OpurqanQ6HT169ODevXvNru3HjRvHzJkzSUlJwdvbW72U0+l03L17F7PZjJubGzqdDr1eT2ZmJjNmzMBkMpGfn6/+lXxc/97e3nh4eFBVVcWePXvUUYyzGDVqlEP6uXPnDkePHqWiooLu3bsTERHR6lA/PT2dvXv3kp2dbXUtZkcZO3Ys69atY+3atbi5uVFdXc3vv//OgAEDMBgMbNq0iXfeeQdAvaXQv39/CgsLAbhx4wZHjx5lypQpj2z/+vXraDQaXn75ZaKjozEajZSUlBAdHU1aWhrFxcXqBMLCwkL1nmhTznp+/wxsDqb4+Hh27tyJn58fvr6+hIWFceTIEaChDMKyZcuIjY3FxcUFd3d39u7dS9++fUlKSsLf3x9PT08KCwvZtWsXb775JuvXr8fFxYWtW7e2qbZLamoqiYmJ6PV6fHx8iImJsfWjPPWuXbvG3bt3iYuLe+z/sBUVFbz33nv069dPnSTn7u7O8ePHHXW4bZKWlsb7779PeHg4Go0GrVbLihUrGDBgAFu2bGHRokWMGjUKNzc3XnvtNZYuXcqMGTNITk4mNDSU/v37ExQU1GL75eXlpKamUl9fj8ViISQkhFdeeQWtVsvnn3/O3Llzqa2t5d69ewwfPpxt27Y58NM3Z835XbBgAYcOHaKqqorx48fj6enJ2bNnHXi09uGiOOqrLCcnFSyFsK6CZXv6844FhRBPLQkmIYTTkWASQjxSaWkpX3zxBeXl5Q7vW4JJCPFInp6elJWVsW3bNnJycqipqXFY3xJMQohH6tWrFwaDAYAzZ87w6aef8uuvvzqkbwkmIUSLIiMj6dq1K9Awn2r79u3k5+e3+3OpEkxCiBZptVqioqKAhtn4iqKQm5vL7t271YnT7UGCSQjRqmHDhj00v8lkMvHZZ5/x22+/tUufEkxCiFa5uroyevToZq8piqJe2rVHoUEJJiHEYwUGBvLMM880e01RFOrr68nKyrL7yEmCSQjxWFqtFoPB8FAlEGgoa2TvWmQdU9nMCTnLM0JCOKvBgwfz3XffAQ2liRRFoU+fPrzxxht2L48iIyYhRJv07NlTrWrZWCersrKy1RpZtpLqAkKINqusrMRiseDr68vWrVupqKhgzJgxREdH27UfGTEJIdqsT58++Pr6AhAaGgo01FK39/hGgkkIYZNBgwap2/ZeaUeCSQhhE61WS2BgIAA//fRTs5+lpqbSr18/XFxcuHDhgtVtSzAJIWzWuLDmg6VRJk2ahNFopG/fvja1K9MFhBA2a1w668EJlhEREU/UroyYhBA2a7qmnz3rNUkwCSFs5uHhoW7X1dXZrV0JJiGEzZouMOru7m63diWYhBA2azpKkmASQjiFO3fuqNuurq7q9ttvv42vry/l5eXExMTw4osvWtWuBJMQwma//PILAF5eXs0qD2zatIny8nLMZjNXrlzh0qVLVrUrwSSEsJnJZALAz8/Pru3KPKb/I0uEC2Fd+R+LxaLO+G6sNmAvMmISQtikuLhY3X7uuefs2rYEkxDCaoqi8O233wINs7ztXcFSgkkIYTWTyaTe/ggJCbF7+xJMQgirmM1mvvzySwBGjhxJ586d7d6HBJMQwionT55UF7t86aWX2qUPCSYhRJtVVFRgNBoBSExMxNPTs136kWASQrRJTU0NmZmZQMOKKUOGDGm3viSYhBCPZTabyczMpL6+HoCEhIR27U+CSQjRKkVR2Lt3L1VVVQDMmTOnXW54N2V1MGVnZzN48GD0ej3nz5+3at+bN2/y0UcfWdul6uDBgyxatOix71u+fDkLFy60uZ8/s0WLFjFs2DB0Ol2zCXLiz8He51dRFI4cOUJJSQkAycnJ9OrV64nbfRyrgykjI4OVK1dSVFSEv7+/Vfs+STCZzWbGjx/Pxx9/bNP+osHrr7/OkSNH1FrNzshsNrdr+xaLBYvF0q59dBR7nt/GUCooKABg4sSJdn/0pCVWBVNqaip5eXksXryYsLAwpk2bRnBwMAEBASQkJHD16lX1vdu3b0ev1zN8+HCCg4MpKytjzpw53Lx5E71eT3BwMACXLl0iJiaGgIAA9Ho9Bw4cUNtwcXHhk08+ITIykiVLlrBjxw4mTZoEwJUrV4iKiiIoKIihQ4eSmppq97WtWqLT6Vi3bh1RUVH4+/uzc+dOh/TbkrKyMnbv3k1xcfFjf+HCw8Px8fFx0JG1nU6nY+PGjYwdO5bly5dz69Yt5s2bR2RkJAaDgfnz56v3NyorK5k+fToGgwGDwcAHH3wANFxibN68WW1z6dKlrF69GoDVq1cze/ZskpKSCA8P58qVK7z77rsEBQURFhZGREQEtbW1AOTm5hIbG0tERARRUVHk5+c7+L9Gcx11fr///ns1lOLj4wkICLBLu21h1TzyDRs2cO7cORYuXEhCQgLXr19Xa/6mpaWxcuVK0tPTOXHiBKtWrSIvL4/evXurcx4yMjIIDg6mqKhIbTMpKYlZs2aRkpLCxYsXCQ0NJSgoSH32pq6ujhMnTgCwY8cOdb9u3bqRk5NDly5duH//PhMmTGDfvn1qcLW3Tp06cfz4cUpKSoiKimLKlCl2n5bfVl5eXnh6enL48GEKCgoICQnBz88PjebpuoVYV1fHoUOHgIY/gmFhYWzcuBFFUZg3bx6bN29m7ty5zJ49m9jYWLKysgC4fv16m9rPy8sjLy8PLy8vzp49y8mTJzl9+jQajYY//vgDd3d3fv75Z9LS0ti/fz86nQ6TycTYsWO5cOECWq223T57azrq/DYuBz5u3DhGjBjRrn096Il+k3bt2kVWVhZ1dXXU1NTg7e0NwNdff01ycjK9e/cGaPFG2a1btygqKmLWrFkADBw4kNGjR2M0Gpk6dSoAM2fOfOS+FouFxYsXYzQaURSFq1evotfrHRZMkydPBhoW/XNzc6Oqquqhv1SnTp2isrLSIccD4OPjQ3V1NYcPH+bYsWMkJiaq5+RpMH36dHX7q6++4vTp06SnpwMNX1VrtVpu375NQUEB2dnZ6nubFsRvTVxcHF5eXgD069eP+vp63nrrLcaMGUNcXBwajYbc3FxKS0uJj49vtm95eflDlzF/9vMbGBjIsGHDOiSQbQ4mo9FIeno6P/zwA15eXhw8eJCVK1da1UbjpVfTAlMP/rtLly6P3Hft2rXcuHGDgoICPDw8WLBggToUd4ROnTqp2xqNpt3vi/wtaDpZT1EUdu/e/VAY3L59u8X93dzcmtWgrq2tbdZm0+2uXbty6tQpjEYjeXl5rFixgm+++QZFUYiJiWHLli32+EhPvY4aJdocTNXV1eh0Onr06MG9e/eaXduPGzeOmTNnkpKSgre3t3opp9PpuHv3LmazGTc3N3Q6HXq9nszMTGbMmIHJZCI/P1/9K/m4/r29vfHw8KCqqoo9e/aooxhnMWrUKIf0c+fOHY4ePUpFRQXdu3cnIiLiqbyUa2rs2LGsW7eOtWvX4ubmRnV1Nb///jsDBgzAYDCwadMm3nnnHQD1lkL//v0pLCwE4MaNGxw9epQpU6Y8sv3r16+j0Wh4+eWXiY6Oxmg0UlJSQnR0NGlpaRQXF6sTCAsLC9V7ok3J+W0/NgdTfHw8O3fuxM/PD19fX8LCwjhy5AjQUAZh2bJlxMbG4uLigru7O3v37qVv374kJSXh7++Pp6cnhYWF7Nq1izfffJP169fj4uLC1q1b21TbJTU1lcTERPR6PT4+PsTExNj6UZ56165d4+7du8TFxT32f9gFCxZw6NAhqqqqGD9+PJ6enpw9e9aBR9s2aWlpvP/++4SHh6PRaNBqtaxYsYIBAwawZcsWFi1axKhRo3Bzc+O1115j6dKlzJgxg+TkZEJDQ+nfvz9BQUEttl9eXk5qair19fVYLBZCQkJ45ZVX0Gq1fP7558ydO5fa2lru3bvH8OHD2bZtmwM/fXN/xvP7OC6Ko77KcnJSwVII6ypYtqc/71hQCPHUkmASQjgdCSYhxCOVlpbyxRdfUF5e7vC+JZiEEI/k6elJWVkZ27ZtIycnh5qaGof1LcEkhHikXr16YTAYADhz5gyffvopv/76q0P6lmASQrQoMjKSrl27Ag3zqbZv305+fn67P5cqwSSEaJFWqyUqKgpomI2vKAq5ubns3r1bnTjdHiSYhBCtGjZs2EPzm0wmE5999hm//fZbu/QpwSSEaJWrqyujR49u9pqiKOql3eXLl+3epwSTEOKxAgMDeeaZZ5q9pigK9fX1ZGVl2X3kJMEkhHgsrVaLwWB4qBIINJQ1snctso6pbOaEnOUZISGc1eDBg/nuu++AhtJEiqLQp08f3njjDbuXR5ERkxCiTXr27KlWtWysk1VZWdlqjSxbSXUBIUSbVVZWYrFY8PX1ZevWrVRUVDBmzBiio6Pt2o+MmIQQbdanTx98fX0BCA0NBRpqqdt7fCPBJISwyaBBg9TtsrIyu7YtwSSEsIlWqyUwMBCAn376qdnPUlNT6devHy4uLly4cMHqtiWYhBA2a1xY88HSKJMmTcJoNNK3b1+b2pXpAkIImzUunfXgBMuIiIgnaldGTEIImzVd08+e9ZokmIQQNvPw8FC36+rq7NauBJMQwmZNFxh1d3e3W7sSTEIImzUdJUkwCSGcwp07d9RtV1dXdfvtt9/G19eX8vJyYmJiePHFF61qV4JJCGGzX375BQAvL69mlQc2bdpEeXk5ZrOZK1eucOnSJavalWASQtjMZDIB4OfnZ9d2ZR7T/5ElwttGysOIRhaLRZ3x3VhtwF5kxCSEsElxcbG6/dxzz9m1bQkmIYTVFEXh22+/BRpmedu7gqUEkxDCaiaTSb39ERISYvf2JZiEEFYxm818+eWXAIwcOZLOnTvbvQ8JJiGEVU6ePKkudvnSSy+1Sx8STEKINquoqMBoNAKQmJiIp6dnu/QjwSSEaJOamhoyMzOBhhVThgwZ0m59STAJIR7LbDaTmZlJfX09AAkJCe3anwSTEKJViqKwd+9eqqqqAJgzZ0673PBuyupgys7OZvDgwej1es6fP2/Vvjdv3uSjjz6ytkvVwYMHWbRo0WPft3z5chYuXGhzP392ly5dIiYmhsDAQCIjI/nv//7vjj4k4aQUReHIkSOUlJQAkJycTK9evdq9X6uDKSMjg5UrV1JUVIS/v79V+z5JMJnNZsaPH8/HH39s0/7i/82fP58ZM2bw448/Mn/+fN5+++2OPiThhBpDqaCgAICJEyfa/dGTllgVTKmpqeTl5bF48WLCwsKYNm0awcHBBAQEkJCQwNWrV9X3bt++Hb1ez/DhwwkODqasrIw5c+Zw8+ZN9Ho9wcHBwP//9Q4ICECv13PgwAG1DRcXFz755BMiIyNZsmQJO3bsYNKkSQBcuXKFqKgogoKCGDp0KKmpqXZf26olOp2OdevWERUVhb+/Pzt37nRIvy0pKytj9+7dFBcXY7FYWn3vtWvXOHv2LJMnTwZgwoQJXL58mcuXLzviUMVT5Pvvv1dDKT4+noCAAIf1bdU88g0bNnDu3DkWLlxIQkIC169fV2v+pqWlsXLlStLT0zlx4gSrVq0iLy+P3r17q3MeMjIyCA4OpqioSG0zKSmJWbNmkZKSwsWLFwkNDSUoKEh99qauro4TJ04AsGPHDnW/bt26kZOTQ5cuXbh//z4TJkxg3759anC1t06dOnH8+HFKSkqIiopiypQpdp+W31ZeXl54enpy+PBhCgoKCAkJwc/PD43m4b875eXleHt7q8fq4uKi1s2xdUUL8efUuBz4uHHjGDFihEP7fqLfpF27dpGVlUVdXR01NTV4e3sD8PXXX5OcnEzv3r0BWrxRduvWLYqKipg1axYAAwcOZPTo0RiNRqZOnQrAzJkzH7mvxWJh8eLFGI1GFEXh6tWr6PV6hwVT44hj0KBBuLm5UVVVhY+PT7P3nDp1isrKSoccD4CPjw/V1dUcPnyYY8eOkZiYqJ6TpprWzQEcNtIUT5fAwECGDRuGVqt1eN82fytnNBpJT0/nm2++4fz586xdu5ba2lqr2mj8hXjwF6Xpv7t06fLIfdeuXcuNGzcoKCjg3Llz/MM//IPV/T+JTp06qdsajQaz2eywvp+Er68vlZWV6vEqikJFRYW67LMQTXVEKMETjJiqq6vR6XT06NGDe/fusXnzZvVn48aNY+bMmaSkpODt7a1eyul0Ou7evYvZbMbNzQ2dToderyczM5MZM2ZgMpnIz88nPT29Tf17e3vj4eFBVVUVe/bsUUcxzmLUqFEO6efOnTscPXqUiooKunfvTkRERIuXcl5eXgQEBPAf//EfJCUlkZ2dzfPPPy+XccKp2BxM8fHx7Ny5Ez8/P3x9fQkLC+PIkSNAQxmEZcuWERsbi4uLC+7u7uzdu5e+ffuSlJSEv78/np6eFBYWsmvXLt58803Wr1+Pi4sLW7dubVNtl9TUVBITE9Hr9fj4+BATE2PrR3nqXbt2jbt37xIXF9diIDX1b//2b8yZM4c1a9ag0+nIyMhw0JEK0TYuitxgAKSCZVtJBUvhCDLzWwjhdCSYhBBOR4JJCOF0JJiEEE5HgkkI4XQkmIQQTkeCSQjhdCSYhBBOR4JJCOF0JJiEEE5HgkkI4XTkWTkhhNOREZMQwulIMAkhnI4EkxDC6UgwCSGcjgSTEMLpSDAJIZyOBJMQwulIMAkhnI4EkxDC6UgwCSGcjgSTEMLpSDAJIZyOBJMQwulIMAkhnI4EkxDC6UgwCSGcjgSTEMLpSDAJIZyOBJMQwun8LzBU5zPIM/5oAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 274x226 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from diagram import diagram, adjust\n",
    "\n",
    "width, height, x, y = [2.74, 2.26, 0.73, 2.05]\n",
    "ax = diagram(width, height)\n",
    "bbox = stack.draw(ax, x, y)\n",
    "# adjust(x, y, bbox)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f924c539",
   "metadata": {},
   "source": [
    "返回值沿着栈向上传递。在每个帧中，返回值是`n`与`recurse`的乘积。\n",
    "\n",
    "在最后一帧中，不存在局部变量`recurse`，因为没有执行创建该变量的分支。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acea9dc1",
   "metadata": {},
   "source": [
    "## 信仰之跃\n",
    "\n",
    "跟随程序执行流程是阅读程序的一种方式，但大量的代码很快就会淹没你。我把另一种可选方式称为“信仰之跃”。当你调用函数时，你*假设*函数能够正确工作，返回正确的值，而不是查看完整的执行流程。\n",
    "\n",
    "实际上，你在使用内建函数时已经练习了“信仰之跃”过程。当你调用`abs`或`math.sqrt`时，你并不检查这些函数的函数体，你只是假设它们有效。\n",
    "\n",
    "当你调用自己的函数时同样也在练习该过程。例如，之前我们编写了`is_divisible`函数来判断一个数能否被另一个数整除。当我们确信这个函数正确，我们就会直接调用它，不再查看函数体。\n",
    "\n",
    "对于递归函数依然如此。当你进行递归调用时，你不应该跟随程序的执行流，而应该假定递归调用有效，然后问自己，“如果我可以计算$n-1$的阶乘，我能够计算$n$的阶乘吗？”阶乘函数的递归定义表明你可以通过乘以$n$来计算。\n",
    "\n",
    "当然，在你还没写完函数之前就假定函数正确有些奇怪，但这也是为什么它叫作“信仰之跃”！"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca2a2d76",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 斐波那契数列\n",
    "\n",
    "除了`factorial`，最常见的递归函数是`fibonacci`，其定义如下：\n",
    "\n",
    "$$\\begin{aligned}\n",
    "\\mathrm{fibonacci}(0) &= 0 \\\\\n",
    "\\mathrm{fibonacci}(1) &= 1 \\\\\n",
    "\\mathrm{fibonacci}(n) &= \\mathrm{fibonacci}(n-1) + \\mathrm{fibonacci}(n-2)\n",
    "\\end{aligned}$$ \n",
    "\n",
    "将其转化为Python代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "cad75752",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif  n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fibonacci(n-1) + fibonacci(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69d56a0b",
   "metadata": {},
   "source": [
    "如果你想要跟随程序的执行流，即使是很小的$n$，你的脑袋也会爆炸。但是通过信仰之跃，如果你假定两个递归调用正确工作，你可以肯定最后的`return`结果正确。\n",
    "\n",
    "顺带一提，这种计算斐波那契数列的方式效率很低。在[Chapter 10](chap10.ipynb)中，将解释为什么，以及一种推荐的改善方式。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26d9706b",
   "metadata": {},
   "source": [
    "## 类型检查\n",
    "\n",
    "如果调用`factorial`并将`1.5`作为参数，会发生什么？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "5e4b5f1d",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31mRecursionError\u001b[0m\u001b[0;31m:\u001b[0m maximum recursion depth exceeded\n"
     ]
    }
   ],
   "source": [
    "%%expect RecursionError\n",
    "\n",
    "factorial(1.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bec7ba4",
   "metadata": {},
   "source": [
    "看起来发生了无限递归。为什么呢？函数有基准条件`n == 0` 和`n == 1`。但当`n`不是整数时，我们会*错过*基准条件，永远递归下去。\n",
    "\n",
    "在这个例子里，初始的`n`为`1.5`，在第一次递归调用中，`n`为`0.5`，下一次递归调用中，`n`为`-0.5`。从此之后，`n`变得越来越小（负），但永远不会为`0`。\n",
    "\n",
    "要避免无限递归，我们可以使用内建的`isinstance`函数检查参数的类型。以下是检查值是否为整数的例子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "3f607dff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isinstance(3, int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "ab638bfe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isinstance(1.5, int)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0017b42",
   "metadata": {},
   "source": [
    "现在新的`factorial`版本将进行错误检查。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "73aafac0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if not isinstance(n, int):\n",
    "        print('factorial的参数n必须为整数。')\n",
    "        return None\n",
    "    elif n < 0:\n",
    "        print('factorial的参数n必须为非负整数。')\n",
    "        return None\n",
    "    elif n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n * factorial(n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0561e3f5",
   "metadata": {},
   "source": [
    "首先它检查`n`是否是整数，如果不是则显示错误信息并返回`None`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "be881cb7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "factorial的参数n必须为整数。\n"
     ]
    }
   ],
   "source": [
    "factorial('crunchy frog')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10b00a39",
   "metadata": {},
   "source": [
    "然后检查`n`是否为负数。如果是负数，显示错误信息并返回`None`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "fa83014f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "factorial的参数n必须为非负整数。\n"
     ]
    }
   ],
   "source": [
    "factorial(-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96aa1403",
   "metadata": {},
   "source": [
    "如果我们通过了两个检查，我们知道`n`是非负的整数。因此我们可以肯定递归能够结束。检查函数的参数，确保它们有正确的类型和值称为**输入验证input validation**。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb8a85a7",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 调试\n",
    "\n",
    "将大程序分解为小函数能够创建天然的调试检查点。如果函数无效，有3种可能的原因：\n",
    "\n",
    "- 函数接受的参数错误，违反了前置条件；\n",
    "- 函数有错误，违反了后置条件；\n",
    "- 调用者对返回值做了错误操作。\n",
    "\n",
    "对于第1种可能，你可以在函数开头添加`print`语句来显示参数的值（以及类型）。你也可以编写代码显式检查前置条件。\n",
    "\n",
    "如果参数看起来没问题，你可以在每个`return`语句前添加`print`语句，显示返回值。如果条件允许，用更易于检查的参数调用函数。\n",
    "\n",
    "在函数的开头和结尾添加`print`语句可以让执行流更明显。例如，以下是带有打印语句的`factorial`版本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "1d50479e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    space = ' ' * (4 * n)\n",
    "    print(space, 'factorial', n)\n",
    "    if n == 0:\n",
    "        print(space, '返回 1')\n",
    "        return 1\n",
    "    else:\n",
    "        recurse = factorial(n-1)\n",
    "        result = n * recurse\n",
    "        print(space, '返回', result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c044111",
   "metadata": {},
   "source": [
    "`space`是控制输出缩进的字符串，由空格组成。以下是`factorial(3)`的结果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "798db5c4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "             factorial 3\n",
      "         factorial 2\n",
      "     factorial 1\n",
      " factorial 0\n",
      " 返回 1\n",
      "     返回 1\n",
      "         返回 2\n",
      "             返回 6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorial(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43b3e408",
   "metadata": {},
   "source": [
    "如果你对执行流感到困惑，这种输出可能更有帮助。开发高效的脚手架需要花一些时间，但一小点脚手架会节省很多的调试时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7c3962f",
   "metadata": {},
   "source": [
    "## 术语表\n",
    "\n",
    "\n",
    "- **返回值return value**：函数的结果。如果函数调用作为表达式，则表达式的值就是返回值\n",
    "- **纯函数pure function**：只会返回值，不显示任何东西或有其他影响的函数。\n",
    "- **死代码dead code**：永远不会执行的代码部分，通常出现在`return`语句之后。\n",
    "- **增量开发incremental development**：旨在避免调试的一种编程开发计划，一次添加并测试少量的代码。\n",
    "- **脚手架scaffolding**：只在程序开发过程中使用的代码，不是最终版本代码的一部分。\n",
    "- **图灵完备Turing complete**：一个语言，或者语言的子集，当它能够执行任何算法的计算时就是图灵完备的。\n",
    "- **输入验证input validation**：检查函数的参数，确保它们有正确的类型和值"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff7b1edf",
   "metadata": {},
   "source": [
    "## 练习"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "e0f15ca4",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Exception reporting mode: Verbose\n"
     ]
    }
   ],
   "source": [
    "# 这个单元格让Jupyter在出现运行时故障时提供更多调试信息。\n",
    "# 在进行练习前先运行本单元格。\n",
    "\n",
    "%xmode Verbose"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0da2daaf",
   "metadata": {},
   "source": [
    "### 询问虚拟助手\n",
    "\n",
    "本章我们看到了一个可能不返回数值的错误函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "90b4979f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value_wrong(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    if x > 0:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69563d4b",
   "metadata": {},
   "source": [
    "以及有死代码的函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "9217f038",
   "metadata": {},
   "outputs": [],
   "source": [
    "def absolute_value_extra_return(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    else:\n",
    "        return x\n",
    "    \n",
    "    return 'This is dead code.'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fe8ae2e",
   "metadata": {},
   "source": [
    "以及一个正确但是不符合习惯的函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "3168489b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_divisible(x, y):\n",
    "    if x % y == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14f52688",
   "metadata": {},
   "source": [
    "询问虚拟助手每个函数的问题，以及修改方案。\n",
    "\n",
    "然后要求它“编写函数，接受两个点的坐标，计算它们之间的距离”。看看它提供的函数是否与本章我们编写的`distance`相似。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd23bb60",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "使用增量开发方式，编写函数`hypot`，接受两条直角边的边长为参数，返回对应直角三角形的斜边长度。\n",
    "\n",
    "注意`math.hypot`做相同的事，但你不应该使用它完成这个练习！\n",
    "\n",
    "即使你能够一次性正确编写函数，也从总是返回`0`的函数开始，练习做出小修改并测试的过程。当你完成时，函数应该只返回值，不应该显示任何信息。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a66d82a",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "编写布尔函数`is_between(x, y, z)`，如果y在x和z之间返回`True`，否则返回`False`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a4ee482",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这编写"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c12f318d",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以用这些例子测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "956ed6d7",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_between(1, 2, 3)  # True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a994eaa6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_between(3, 2, 1)  # True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4318028d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_between(1, 3, 2)  # False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05208c8b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_between(2, 3, 1)  # False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57f06466",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "阿克曼函数$A(m, n)$定义为：\n",
    "\n",
    "$$\\begin{aligned}\n",
    "A(m, n) = \\begin{cases} \n",
    "              n+1 & m = 0 \\\\ \n",
    "        A(m-1, 1) & m > 0,n = 0 \\\\ \n",
    "A(m-1, A(m, n-1)) & m > 0,n > 0.\n",
    "\\end{cases} \n",
    "\\end{aligned}$$ \n",
    "\n",
    "编写函数`ackermann`计算阿克曼函数。如果调用`ackermann(5, 5)`会发生什么？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7eb85c5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这编写"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85f7f614",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用以下示例进行测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "687a3e5a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "ackermann(3, 2)  # 29"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c49e9749",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "ackermann(3, 3)  # 61"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8497dec4",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "ackermann(3, 4)  # 125"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4994ceae",
   "metadata": {
    "tags": []
   },
   "source": [
    "如果你用超过4的值调用该函数，将导致`RecursionError`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76be4d15",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect RecursionError\n",
    "\n",
    "ackermann(5, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8af1586",
   "metadata": {
    "tags": []
   },
   "source": [
    "添加打印语句到函数的开头，显示参数的值，然后重新运行示例，检查为什么会这样。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c2ac0a4",
   "metadata": {
    "tags": []
   },
   "source": [
    "### 练习\n",
    "\n",
    "若数字$a$是$b$的幂(power)，则$a$可以被$b$整除，且$a/b$也可以被$b$整除。编写递归函数`is_power`，接受参数`a`与`b`，如果`a`是`b`的幂，则返回`True`，否则返回`False`。注意：必须考虑基准条件。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0bcba5fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这编写"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e93a0715",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用以下示例进行测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b6656e6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_power(65536, 2)   # True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36d9e92a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_power(27, 3)  # True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d944b42",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_power(24, 2)  # False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63ec57c9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "is_power(1, 17)   # True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6319c30",
   "metadata": {},
   "source": [
    "译注：$17^0==1$，考虑该特殊情况与练习中幂的判定方法，设置基准条件。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a33bbd07",
   "metadata": {},
   "source": [
    "### 练习\n",
    "\n",
    "$a$和$b$的最大公约数(GCD)是可以同时将它们整除的数的最大值。\n",
    "\n",
    "一种求最大公约数的方法基于以下观察：如果$a$除以$b$的余数为$r$，那么$gcd(a,\n",
    "b) = gcd(b, r)$。基准条件为$gcd(a, 0) = a$。\n",
    "\n",
    "译注：也即辗转相除法。\n",
    "\n",
    "编写函数`gcd`，接受参数`a`,`b`，返回最大公约数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e067bfb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在这编写"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efbebde9",
   "metadata": {
    "tags": []
   },
   "source": [
    "你可以使用以下示例进行测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a7c1c21",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "gcd(12, 8)    # 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5df00229",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "gcd(13, 17)   # 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7f4edf8",
   "metadata": {
    "tags": []
   },
   "source": [
    "[Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html)\n",
    "\n",
    "Copyright 2024 [Allen B. Downey](https://allendowney.com)\n",
    "\n",
    "Code license: [MIT License](https://mit-license.org/)\n",
    "\n",
    "Text license: [Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-nc-sa/4.0/)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
